/**
 * https://leetcode.cn/problems/accounts-merge/submissions/576379147/
 * 721. 账户合并
 * medium,陈贝纯 2024.10.28
 * 并查集
 */


class Solution {
public:
    map<string,string> parent;
    unordered_map<string,string> person;
    void pair(string a,string b){
        parent[find(b)]=find(a);
    }
    string find(string rep){
        if(parent[rep]!=rep)
            parent[rep]=find(parent[rep]);
        return parent[rep];
    }
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        for(int i=0;i<accounts.size();++i){
            for(int j=1;j<accounts[i].size();++j){
                parent[accounts[i][j]]=accounts[i][j];
                person[accounts[i][j]]=accounts[i][0];
            }
        }
        for(int i=0;i<accounts.size();++i){
            for(int j=2;j<accounts[i].size();++j){
                pair(accounts[i][1],accounts[i][j]);
            }
        }
        for(int i=0;i<accounts.size();++i){
            for(int j=1;j<accounts[i].size();++j){
                find(accounts[i][j]);
            }
        }
        vector<vector<string>> vt;
        while(!parent.empty()){
            vector<string> v;
            auto it=parent.begin();
            string rep=it->second;
            v.push_back(person[it->second]);
            for(;it!=parent.end();){
                if(it->second==rep){
                    v.push_back(it->first);
                    it=parent.erase(it);
                }else
                it++;
            }
            vt.push_back(v);
        }
        return vt;
    }
};